package C051;

/**
 * ClassName: C07
 * Package: C051
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/3/17 14:31
 * @Version 1.0
 * @Since 1.0
 */
public class C07 {
    // 对数器测试
    public static void main(String[] args) {
        // 随机测试的数据量不大
        // 因为数据量大了，fast1方法会超时
        // 所以在数据量不大的情况下，验证fast2方法功能正确即可
        // fast2方法在大数据量的情况下一定也能通过
        // 因为时间复杂度就是最优的
        System.out.println("测试开始");
        int N = 30;
        int V = 20;
        int H = 300;
        int testTimes = 10000;
        for (int i = 0; i < testTimes; i++) {
            int n = (int) (Math.random() * N) + 1;
            int[] cuts = randomArray(n, V);
            int[] posions = randomArray(n, V);
            int hp = (int) (Math.random() * H) + 1;
            int ans1 = fast1(cuts, posions, hp);
            int ans2 = process(cuts, posions, hp);
            if (ans1 != ans2) {
                System.out.println("出错了!");
            }
        }
        System.out.println("测试结束");
    }

    // 对数器测试
    public static int[] randomArray(int n, int v) {
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = (int) (Math.random() * v) + 1;
        }
        return ans;
    }


    // 动态规划方法(只是为了验证)
    // 目前没有讲动态规划，所以不需要理解这个函数
    // 这个函数只是为了验证二分答案的方法是否正确的
    // 纯粹为了写对数器验证才设计的方法，血量比较大的时候会超时
    // 这个方法不做要求，此时并不需要理解，可以在学习完动态规划章节之后来看看这个函数
    public static int fast1(int[] cuts, int[] poisons, int hp) {
        int sum = 0;
        for (int num : poisons) {
            sum += num;
        }
        int[][][] dp = new int[cuts.length][hp + 1][sum + 1];
        return f1(cuts, poisons, 0, hp, 0, dp);
    }

    // 不做要求
    public static int f1(int[] cuts, int[] poisons, int i, int r, int p, int[][][] dp) {
        r -= p;
        if (r <= 0) {
            return i + 1;
        }
        if (i == cuts.length) {
            if (p == 0) {
                return Integer.MAX_VALUE;
            } else {
                return cuts.length + 1 + (r + p - 1) / p;
            }
        }
        if (dp[i][r][p] != 0) {
            return dp[i][r][p];
        }
        int p1 = r <= cuts[i] ? (i + 1) : f1(cuts, poisons, i + 1, r - cuts[i], p, dp);
        int p2 = f1(cuts, poisons, i + 1, r, p + poisons[i], dp);
        int ans = Math.min(p1, p2);
        dp[i][r][p] = ans;
        return ans;
    }


    // cuts 是刀砍， poisons 是毒药, hp 是boss的血量
    // 前面的两个数组的元素都是非负的
    public static int process(int[] cuts, int[] poisons, int hp) {
        // 假设 攻击只有1，最大的回合数就是 hp + 1
        int l = 0, r = hp + 1, mid;
        int ans = 0;
        while(l <= r) {
            mid = l + ((r - l) >> 1);
            if(f(cuts, poisons, hp, mid)) {
                ans = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return ans;
    }


    // 在 limit 的回合次数下，是否可以击败怪兽
    private static boolean f(int[] cuts, int[] poisons, int hp, int limit) {
        int n = Math.min(cuts.length, limit);
        for (int i = 0; i < n; i++) {
            hp -= Math.max(cuts[i], (limit - i - 1) * poisons[i]);
            if(hp <= 0) {
                return true;
            }
        }
        return false;
    }

}
